package com.cqs.leetcode;

/**
 * Created by cqs on 2018/3/29.
 */
public class BalancedBinaryTree {

    private TreeNode root;

    private void buildTree(Integer[] nodes) {
        TreeNode[] tree = new TreeNode[nodes.length];
        for (int i = nodes.length - 1; i >= 0; --i) {
            if (nodes[i] != null) {
                TreeNode node = new TreeNode(nodes[i]);
                tree[i] = node;
                if ((2 * i + 1) < nodes.length) {
                    node.left = tree[2 * i + 1];
                }
                if ((2 * i + 2) < nodes.length) {
                    node.right = tree[2 * i + 2];
                }
            }
        }
        if (nodes.length > 0) {
            root = tree[0];
        }
    }

    public boolean isBalanced(TreeNode root) {
        int rh = high(root.right);
        if (rh == -1) return false;
        int lh = high(root.left);
        return lh != -1 && Math.abs(rh - lh) < 2;
    }

    /**
     * 高度为-1表示node为根的子树不平衡
     *
     * @param node
     * @return
     */
    private int high(TreeNode node) {
        if (node == null) return 0;
        int lh = high(node.left);
        if (lh == -1) return -1;
        int rh = high(node.right);
        if (rh == -1)
            return -1;
        if (Math.abs(lh - rh) < 2)
            return 1 + Math.max(lh, rh);
        else
            return -1;
    }

    public static void main(String[] args) {
        BalancedBinaryTree tree = new BalancedBinaryTree();
//        Integer[] nodes = {1, 2, 2, 3, 3, null, null, 4, 4};
        Integer[] nodes = {3, 9, 20, null, null, 15, 7};
        tree.buildTree(nodes);
//        System.out.println(tree.high(tree.root));
        boolean balanced = tree.isBalanced(tree.root);
        System.out.println(balanced);
    }


}




